package com.example.question.tree.tree1;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Date 2023-07-08
 * @Author Jonathan
 * 二叉树的一般方法
 */
public class Tree {
    private static int index; // 全局索引变量

    public static void main(String[] args) {
//        TreeNode tree = createTree(new Integer[]{1, null, 2, 3, null, null, null});
        TreeNode tree = createTree(new Integer[]{3, 9, null, null, 20, 15, null, null, 7, null, null});
        System.out.println(preorderTraversal(tree));
    }

    public static TreeNode createTree(Integer[] nums) {
        index = 0; // 初始化索引变量
        return createTreeHelper(nums);
    }

    public static TreeNode createTreeHelper(Integer[] nums) {
        if (index >= nums.length || nums[index] == null) {
            index++; // 跳过 null 节点
            return null;
        }
        TreeNode treeNode = new TreeNode(nums[index]);
        index++; // 增加索引
        treeNode.left = createTreeHelper(nums);
        treeNode.right = createTreeHelper(nums);
        return treeNode;
    }

    /**
     * 输入的数组需要符合预期的二叉树结构
     */
//    public static TreeNode createTree(Integer[] nums) {
//        if (nums == null || nums.length < 1) {
//            return null;
//        }
//        return createTree(nums, 0);
//    }
    public static TreeNode createTree(Integer[] nums, int index) {
        if (index >= nums.length) {
            return null;
        }
        // 三元表达式
        TreeNode treeNode = new TreeNode(nums[index]);
        if (nums[index + 1] == null) {
            treeNode.left = null;
        } else {
            treeNode.left = createTree(nums, ++index);
        }
//        treeNode.left = nums[index + 1] == null ? null : createTree(nums, index + 1);
        if (nums[index + 2] == null) {
            treeNode.right = null;
        } else {
            treeNode.right = createTree(nums, ++index);
        }
//        treeNode.right = nums[index + 2] == null ? null : createTree(nums, index + 2);
        return treeNode;
    }


    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ret.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return ret;
    }

}
